package com.lw.leetcode.arr.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * c
 * arr
 * 1889. 装包裹的最小浪费空间
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/7 15:10
 */
public class MinWastedSpace {


    public static void main(String[] args) {
        MinWastedSpace test = new MinWastedSpace();


        // 6
//        int[] packages = {2, 3, 5};
//        int[][] boxes = {{4, 8}, {2, 8}};

        // -1
        int[] packages = {2, 3, 5};
        int[][] boxes = {{1, 4}, {2, 3}, {3, 4}};

        // 9
//        int[] packages = {3, 5, 8, 10, 11, 12};
//        int[][] boxes = {{12}, {11, 9}, {10, 5, 14}};

        int i = test.minWastedSpace(packages, boxes);
        System.out.println(i);
    }

    public int minWastedSpace(int[] packages, int[][] boxes) {
        Arrays.sort(packages);
        int size = 100001;
        long[] sums = new long[size];
        long[] counts = new long[size];
        int max = 0;
        for (int v : packages) {
            sums[v] += v;
            counts[v] += 1;
            max = Math.max(max, v);
        }
        for (int i = 1; i <= max; i++) {
            sums[i] += sums[i - 1];
            counts[i] += counts[i - 1];
        }
        long min = Long.MAX_VALUE;
        for (int[] box : boxes) {
            Arrays.sort(box);
            if (box[box.length - 1] < max) {
                continue;
            }
            long all = 0;
            int last = 0;
            for (int v : box) {
                if (v > max) {
                    all += ((counts[max] - counts[last]) * v - (sums[max] - sums[last]));
                    break;
                }
                all += ((counts[v] - counts[last]) * v - (sums[v] - sums[last]));
                last = v;
            }
            min = Math.min(min, all);
        }
        return Long.MAX_VALUE == min ? -1 : (int) (min % 1000000007);
    }

}
